Hello, you will need a backup to be able to restore your accounts. Or an additional 2nd factor authentication method registered so you can access https://mysignins.microsoft.com/security-info (for work or student accounts) or https://account.live.com/proofs/manage/additiona (for personal accounts) and add your new phone. Of the previous is not possible then you will need to contact your Organization Admin (work or student accounts) so he can add the phone or use https://account.live.com/acsr (personal accounts) so you can recover access to your account.
Please let me know if you need more help. If the answer was helpful to you, please accept it and, optionally, provide feedback so that other members in the community can benefit from it.