A Microsoft app for iOS and Android devices that enables authentication with two-factor verification, phone sign-in, and code generation
I'm not a Microsoft support agent, but I've dealt with this kind of issue before and want to point you in the right direction.
Since this is a work account, the fastest fix is to contact your company's IT helpdesk and ask them to reset your MFA registration in Microsoft Entra (Azure AD). They can do this in minutes, and it completely bypasses the 30-day waiting period. This waiting period only applies to self-service resets, not admin-initiated ones.
When you reach IT, specifically ask them to:
1. Reset your MFA methods in the Microsoft Entra admin center, or
2. Issue you a Temporary Access Pass (TAP). This is a one-time code that lets you log in and re-register your Authenticator app on your new phone.
If, for some reason, you don't have an IT admin, you can try Microsoft's account recovery at account.live.com/acsr or call their support line directly at 1-800-642-7676
Hope that gets you back in quickly!