Dessa vez já era, vc precisa entrar em contato com o site e pedir pra que eles desliguem o 2fa da sua conta. Mas aqui vão algumas dicas pras próximas vezes:
1- Faça backup do código de barras ou do codigo de 2FA que os sites geram pra você. Sempre que for ativar 2FA em algum site, IMPRIMA o codigo de barras e guarde ele em um local seguro (ou então, se preferir, capture a tela e salve em um pen-drive).
2- Use Authy ou outro software que permita fazer backup dos seus 2FA. O software do google authenticator é uma droga porque não permite backup do 2FA.
3- Se for paranoico, tenha 2 dispositivos com 2FA. Pegue um celular velho ,e sempre que ativar o 2FA, escaneie o codigo de barras com os dois celulares: o seu "normal" e o celular velho de backup.
4- E por ultimo, lembre SEMPRE de desativar o 2FA em todos os sites antes de formatar o celular.
5-Abre o Google Authenticator, e nos "três pontinhos" escolhe a opção "Transferir contas" e ele cria um código QR para importar as contas.