Authorization method change and log in issues

monikahds I think this is not a SharePoint issue but rather an Identity/Security topic.

The behavior depends also on the Identity Governance your client put in place.

Normally they should have configured an alternative sign-in method as break glass procedure like call/text phone, etc...

If they have done it, then you should be able to access your own page: https://myaccount.microsoft.com/ , Click on the Security Info Tab and generate the QR code for your new mobile.

If you cannot access your account via browser, the only option is to get in contact with their IT department.

The M365 admin needs to temporary disable MFA for your account so you can access again and remove the lost device.

After that, he/she will enable again the MFA so that you can configure the Authenticator app on the new phone.