I did some more research. It looks like there is a way to recover if you don't have the phone number or the old device. They have an online form you fill out with your old phone number and new phone number. Then they have some process to verify ownership of the phone numbers which they say will take several days for security purposes.
https://support.authy.com/hc/en-us/articles/115001953247-Pho...