Option 1: If you can still access your O365 account, you can go to https://mysignins.microsoft.com/security-info and change the phone number associated with your sign-in.
Option 2: Manually transfer your accounts. Go into each account, disable them, then re-enable each one on the new phone.
Option 3: Not too certain about this option with this specific situation of a new phone number, but recovering from a backup if you have one, [https://support.microsoft.com/en-us/account-billing/back-up-and-recover-account-credentials-in-the-authenticator-app-bb939936-7a8d-4e88-bc43-49bc1a700a40.
Please accept as an answer if this was helpful.