Hi @Diego
Thank you for posting your question in the Microsoft Q&A forum.
I'm really sorry to hear you're having trouble accessing your account after switching to a new phone. Since you no longer have access to your old phone and the Authenticator app wasn't set up on your new device, the best solution is to contact your organization's IT support team or administrator. They can assist in resetting your multi-factor authentication settings and guide you through re-registering your account on the new phone. May I know if you know any Global Administrators in your organization who could help with this process?
If yes, please ask them to follow this article to proceed to reset your 2FA so that you could re-register again: Manage authentication methods for Microsoft Entra multifactor authentication - Microsoft Entra ID | Microsoft Learn
If no, then you are the only Global Administrator and you are completely locked out from the tenant. You might need to contact us via phone service number: Customer service phone numbers - Microsoft Support. The agent will be able to create a ticket for you under the affected tenant and then transfer this ticket to DataProtection team who could help you to regain access.
Please note that this team is always overwhelmed, so you might need to wait for them to call you, this should take 3-10 working days. I know that this is not a convenient solution to hear but it seems to be the only way, and it's recommended that you should have a secondary/backup Global Administrator to fix this issue on your own.
If the answer is helpful, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment".
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.