There has been a possibility to back up your Microsoft Authenticator’s multi-factor authentication accounts to iCloud for a long time. All Android users have been waiting this feature since it was published to the iOS-devices.
Today my Android got a new version of Microsoft Authenticator that includes also the cloud backup. Just go to the settings and turn it on. Authenticator asks you to provide a personal Microsoft account where to store the information. It will not allow you to store the information in Work or School account. Hopefully this feature is going to be enabled some day.
Anyway… This helps a LOT of the change of the mobile device, because you don’t have to re-enroll every account in your Microsoft Authenticator. To find closer information, please consult Microsoft’s documentation.
PS. If you are not yet using Microsoft Authenticator, I encourage you do so! Enable Multi factor authentication to every account that you have in any service