Olá
Se esta for uma conta corporativa/de estudante, entre em contato com a TI da sua organização e peça que eles redefinam sua MFA, para que você possa configurar a autenticação novamente no novo telefone.
Se esta for uma conta pessoal,
Se você estiver na página de login e não conseguir acessar seu aplicativo de autenticação, clique em "Não consigo usar meu aplicativo agora". Em seguida, procure uma opção como "Mostrar mais métodos de verificação" para ver se você tem um backup (por exemplo, um número de telefone ou e-mail alternativo).
Se você não tiver acesso a nenhuma das opções listadas, selecione "Não tenho nenhuma dessas". Isso iniciará o processo de recuperação. Como parte desse processo, a Microsoft permitirá que você adicione novas informações de contato – mas somente após um período de espera de 30 dias.
Esse atraso de 30 dias é intencional. É uma proteção de segurança projetada para proteger os usuários caso outra pessoa tente sequestrar sua conta alterando as informações de recuperação. A espera dá ao legítimo proprietário tempo para perceber e interromper alterações não autorizadas.
Infelizmente, essa política não pode ser contornada. Você pode ler mais sobre isso diretamente da Microsoft aqui: