Hello @Eliot Scharf
Thank you for reaching out. If you had backed up your Authenticator App accounts, then you should be able to restore them using following steps:
- Open Microsoft Authenticator on the new phone.
- Tap on Restore from backup or Begin recovery depending on the screen that you are on. The option is near the bottom of the screen.
- Login to your Microsoft account (or iCloud account) that contains the Cloud backup.
- Wait for the restore to complete. Depending on the number of accounts, it can take a few moments.
- Choose from Set up phone sign-in or only enable two-step verification. Phone sign-in is the ideal choice if you have Microsoft accounts in the app.
- The restore will be complete in a few moments. Some of your accounts may require additional verification after the restore.
For details about Microsoft Authenticator Account Backup and Recovery please review following document: Back up and recover account credentials in the Authenticator app
If you still face issues you can work with your organizations admin to trigger a re-register for MFA on your work account: Manage user authentication options - Require Re-register MFA makes it so that when the user signs in next time, they're requested to set up a new MFA authentication method.
I hope this helps.
----------
Please "Accept the answer" if the information helped you. This will help us and others in the community as well.