Locked out from my Azure Portal

Did you have cloud backup switched on in Authenticator before you changed phones? If so, installing it on the new phone and signing into the same recovery account should bring your accounts back.

Also is this a work or school account, or a personal Microsoft account. Work or school means an admin in your tenant has to clear your authentication methods. A Global Administrator or Authentication Administrator can do it in minutes.

Personal means Microsoft's own recovery path. If you know your password, start a sign-in and choose Verify your identity prompt security info replacement, which has a mandatory 30-day wait. If you've lost the password too, it's the recovery form at account.live.com/acsr instead.

Help make this community better for everyone: if this answer resolved your issue, please accept it or leave an upvote. If not, share more details in a comment so we can continue the discussion and find the right solution.