Make sure that your Authenticator is up to date in Play Store. Also try both options, refer below link.
Same-device registration from a browser (Android)
Cross-device registration (Android)
Remove the entry in Microsoft Authenticator app login.microsoft.com and try again.