Hi @Nishanth
If it's not possible to use a backup to restore Authenticator configuration on your new phone , unfortunately , the only solution is to ask your administrator to reset your MFA registration for your Azure account. For other sites you have to use recovery process for each site in case of lost of your phone.
Please don't forget to accept helpful answer