TOTP is bad 2FA. Google supports U2F security keys. Use them.
But yeah, this is why I dislike 2FA. There are clear security benefits, but it comes with the extreme downside of "what you know is not sufficient".
When it's e.g. a corporate-controlled account and your IT desk can just reset it to "password123!" to let you back in, it's quite a good trade-off. When it's your main email, i.e. your primary online identity, losing access is kinda a big deal, and Google has famously bad support.
But that's not even the problem here. OP has the "what you have". Just because the secondary authentication device is made of paper doesn't mean it's any less valid. But google is rejecting it and demanding the lost device.
So... sorta yes, sorta no. What they have is a ticking time bomb which goes off at the whim of a company that clearly does not care about them. That's not really "an authentication device" that anyone would willingly choose.
How so? The only downside is that you have to glance up and make sure you're on a google.com domain before entering it, in exchange for which you get massively simpler implementation, a wider variety of options, and the ability to back up token if you really want.