A Microsoft app for iOS and Android devices that enables authentication with two-factor verification, phone sign-in, and code generation
If the authenticator backup hadn't been performed before the deletion occurred, it can't be used to recover the accounts it held before the deletion, only those accounts that are created in the future.
The authenticator account data is stored in the secure portions of your phone such as the Google Titan M security chip, which both aren't able to be copied from one device to another when upgrading phones and will also be lost if an app storing data within it such authenticator is deleted or the phone is factory reset, which destroys the linkage to the secure data.
This is what you likely did wrong, so you need to understand that data stored in the Titan M or similar chip in an iPhone device aren't like other data and that's why they must be backed up and restored separately as documented by Microsoft for their authenticator.
Back up your accounts in Microsoft Authenticator | Microsoft Support
Since based on your post, it appears you were oblivious to this requirement, the data still stored in the secure chip became unrecoverable once the app was deleted, so no, it can't be recovered in any other way and only by contacting each organization for which you had accounts and setting these back up again using either their individual 2FA recovery process or in a few cases, setting up an entirely new account, can you recover your access to these 3rd-party accounts.
Unfortunately, a few organizations (and many consumer users) seem to be oblivious to these inherent issues with authenticator apps and assume that their customers know these details, leading to quite a few lost credentials (accounts) for those who don't actually read all of the information about these highly secure apps before using them. Unlike past security and IT professionals like me, most consumers aren't technically aware and used to reading extensively before using apps, since to the average person, an app is simply something you install and delete whenever you wish and not a critical security item that requires deep understanding and careful management.
This is why Microsoft and other industry players like Google, Apple and others are switching quickly to passkeys for this sort of 3rd-party website security, as well as their own sites, since consumers are inherently impatient and lazy, so the security objects they use must be as simple and idiot proof as possible, which though still a work in process is quickly getting better by allowing the phishing-resistant passkeys to be backed up to the cloud automatically and synced to multiple devices, in Microsoft's case via the Edge web browser on now both all Windows 10/11 devices and those running either Edge for Android or iOS, which means the technically uneducated consumer only has to learn how to initially accept and install these passkeys, initially install the Edge browser and enable passkeys on their phones and learn how they can be used on their various devices.
What are passkeys and why they matter | Microsoft Support
I've only recently begun using passkeys extensively myself, though I had installed one for Amazon.com on a Windows 10 tablet device several months ago, which I only recently noticed was also available on my phone due to the added syncing ability for the Edge browser's - Microsoft Password Manager I use there and makes logging into that website much easier.
The fact it's on both the tablet and phone also means it's stored in the cloud, so the sync and backup were silent and automatic. I just installed a passkey for logging into multiple US government websites last night using an ID verification service that will avoid needing to setup multiple individual accounts on several of these like Social Security, the IRS, Treasury, and others, which immediately became available on my phone as well.
So, look into whether your devices support at least Windows 10 and preferably 11, since that's simpler to use, and install and use the version of Edge for Android or iOS that works on your device, since that's really the direction Microsoft is going in the future to avoid issues like you've just had with the much more technically difficult to use authenticator.
Create and save a passkey | Microsoft Support
You may be forced to continue to use the authenticator app for at least some websites for the near future, since some like Work or School accounts and quite a few smaller 3rd-party websites have yet to support them, but even if that's true, it's still better to use the passkeys where you can, since having both for a website isn't a problem and only makes it easier when they're available, while eventually all websites will need to support them and even Schools and Workplaces will realize they're easier for their users and thus actually more secure due to less potential user errors and issues. The authenticator apps also have the advantage of being used on either Work or School provided devices like desktops in the office or labs, so they're likely to remain useful for those devices which may be shared and/or not able to have your own personal apps including the Microsoft Password Manager installed.
Rob