When you change smartphones, multi-factor authentication must move to the new device. This is easiest while the old smartphone still works. So only reset the old device afterwards.
Steps (old smartphone still available)
On the new smartphone, install Microsoft Authenticator: App Store, Google Play
On your computer, open Security info and sign in with your company account. Approve the sign-in with the old smartphone.
Choose Add sign-in method › Microsoft Authenticator and click Next until a QR code appears.
On the new smartphone, tap + › Work or school account › Scan QR code in the app and scan the code.
On the computer, click Next and approve the test request on the new smartphone.
Find the old smartphone in the list and click Delete.
Only now reset the old smartphone.
Old smartphone lost or broken?
Then you can no longer sign in. Please contact support. it-tects resets multi-factor authentication, and you then set it up again on the new smartphone, see “Set up multi-factor authentication (MFA) – Microsoft 365”.
Tip
In the app under Settings, turn on backup (iPhone: iCloud Backup, Android: Cloud backup). Work accounts often still need to be verified again after a restore. The steps above are therefore the safe way.