Steps to follow:
Make sure to have Microsoft Authenticator downloaded in your new phone
Step 1 - On your computer, go to: myaccount.microsoft.com
Step 2 - When prompted to authenticate your login with the Microsoft Authenticator app, click Sign in another way or I can't use my Microsoft Authenticator app right now.
Step 3 - Choose your alternate authorization methods and enter the code from your chosen authorization method and click Verify.
Step 4 – Once inside the account, Click on the Update Info button.
Step 5 – Select and delete your old Microsoft Authenticator method from your list of methods.
Step 6 - Click Add sign-in method.
Step 7 - Click the Choose a method drop down and select Authenticator app
Step 8 - Click Next after the Microsoft Authenticator app is installed on your phone.
Step 9 - In the app, click Add account or the Plus Sign +. Select Work or School account and the option to Scan QR Code.
Step 10 - If prompted, Allow the app to Access the Camera.
Step 11 - Use your phone to scan the QR code that appears on the computer screen. After you scan the code, click Next.
Step 12 - If prompted, Allow the Authenticator app to Send You Notifications.
Step 13 - On your phone, Approve the test notification from Microsoft Authenticator
Step 14 - You're all set and can now use the Microsoft Authenticator app for multi-factor authentication (MFA).
Completed
MFA for M365 is now set up on your new or different phone or device.