Olá @Claudio Mauad,
Obrigada por realizar a sua pergunta utilizando a Plataforma Q&A da Microsoft.
Nesse artigo da MS você encontrará diversas maneiras para tentar recuperar o seu authenticator.
Caso não seja possível, entre na página https://aka.ms/mfasetup para verificar os seus métodos de verificação.
Ou melhor ainda, ao chegar na segunda janela, existe uma opção de: NÃO CONSIGO USAR O MEU APLICATIVO MICROSOFT AUTHENTICATOR AGORA. Nessa opção podrá registrar um novo numero de telefone ao que Microsoft lhe realizará uma ligação para confirmar seus datos.
Que tenha um bom día.
Atenciosamente,