Sirisha_Dudiki
I just suffered with this issue when upgrading to a new iPhone. I was stung a few months ago when I restored my previous phone from backup too. Both times made absolutely sure the backup was enabled in the Authenticator app and the date/time of the backup was current. Sure enough, fired up the authenticator app and got "There is no backup stored in your iCloud account. Make sure that you're signed in to the same iCloud account you used to create a backup". Same apple id both times.
From the logs it looks like the app is deleting the backup on first run when it detects no "MSA" account.
2021-09-24 21:21:20.750 VERB PhoneFactor 0 TID=13 219 (updateCloudBackupIfNeeded()) There is MSA backup metadata, but the MSA account is gone. Delete backup.
2021-09-24 21:21:20.750 VERB PhoneFactor 0 TID=13 148 (deleteBackup(backupName:completionHandler:errorHandler:)) Deleting backup with name Backup
2021-09-24 21:21:20.751 VERB PhoneFactor 0 TID=13 113 (delete(containerIdentifier:completionHandler:errorHandler:)) Deleting a CloudKitContainer with name:Backup type:MicrosoftAuthenticatorBackup from the CloudKit storage.
Submitted a ticket through the App, hopefully someone is looking into this, but I’d say it’s not been working for several months. Incident RMCHXANW.