Steps should have been create an authenticator cloud backup on old phone then on new phone you can restore from the authenticator cloud backup but make sure no accounts have been added to the newly install app. Then sign on with recovery account to do the restore.
You can recover your account credentials from your cloud account, but you must first make sure that the account you're recovering doesn't exist in the Microsoft Authenticator app. For example, if you're recovering your personal Microsoft account, you must make sure you don't have a personal Microsoft account already set up in the authenticator app. This check is important so we can be sure we're not overwriting or erasing an existing account by mistake. https://support.microsoft.com/en-us/account-billing/back-up-and-recover-account-credentials-in-the-authenticator-app-bb939936-7a8d-4e88-bc43-49bc1a700a40
and of course we wouldn't want to format old phone until new phone is confirmed as working. Also since Azure is involved be sure to create an emergency access account (break glass) in Azure AD. This account will help prevent being accidentally locked out of your Azure Active Directory (Azure AD) organization because you can't sign in for any reason. https://docs.microsoft.com/en-us/azure/active-directory/roles/security-emergency-access
-
--please don't forget to close up the thread here by marking answer if the reply is helpful--