Your situation is unfortunate. I do not work for Microsoft, and is a user just like you.
If your company purchased your license from a reseller, and have given them delegated admin access, then they would be able to reset your account for you.
Microsoft does typically ask for the admin to provide a secondary validation method, but in your case this might not apply since the phone is lost

Typically as a best practice, it is always a good idea to have a emergency access account or a backup admin, just in case the primary admin is not reachable (or the authentication device is lost).
The second best practice is for admins, to use a normal account for daily work. The global admin account is set to validate via token (like a fido2 key). These account credentials and token are kept in a safe place and used only as necessary. This would prevent the problem your company is facing.
In your case, you have to raise a support ticket via phone
If you are using a global admin account, the best course of action is to reach out to Microsoft’s Data Protection Customer service phone numbers - Microsoft Support.
For some countries, it will be an automated conversation like: First, when you call the hotline, it asks what kind of problem you are worried about.
Answered: authenticator.
A: What kind of product are you using?
B: Office 365 for business.
A confirmation: education or company account?
B: For companies
A: Are you an administrator?
B: Yes.
A: Do you have the other admin in your organization?
B: No.
A: You need one.... Service request?
B: Yes
Due to the possibility of social engineering, the data protection team validation process is tough.
Typical resolution time from previous posts in this forum can take 2-3 weeks after your support ticket has been successfully lodged. Only advice I can provide is be persistent and keep checking and asking them to escalate.
I trust that your users are still able to access their M365 services with only the admin access being affected?
Warm Regards