It happened to me, I had configured the Microsoft Authentication app in my phone and then I changed the phone, so the experience to recreate all the MFA accounts, was simply horrible… but now Microsoft Authenticator allows to backup your multi factor accounts and recover them.
It works for both personal and work profiles, the only requirement is to have a Microsoft Account (MSA) to backup your Microsoft Authenticator application; even if you use it from the device work profile. Something important: You can not use Corporate account to backup your Microsoft Authenticator application.
To enable the backup capability, just access the Options menu (the 3 dot shown at the top right of the application) and choose to Turn on backup – or access the Settings and enable the Cloud Backup feature.
It will then automatically use your MSA account
Keep in mind that, once you have enabled the backup for one instance, and try to enable it on the second one, you will be requested if you want to overwrite it if you use the same MSA account