So this goes to two options first of you have your old phone or have backed up this to your cloud and second if you don't have previous access
If old phone is there then go to settings then backup and turn it ON. Then would be able to restore it from cloud (Can use Normal searches or AI for steps if needed).
If you have no backup at all then can use recovery codes,SMS or Voice calls,Backup Email Address,Backup Keys, Admin Reset,Setting up whole app again
Ask your tenant/global admin to:'Re-register multifactor authentication forthis user" in Azure AD -> Users -> Authentication methods.