You can restore from a cloud backup (created on old phone) 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
The other option is to have the work admins reset the account so a new QR code can be generated with which you can link the new device to your account.
-
--please don't forget to upvote
and Accept as answer
if the reply is helpful--