If you use a nice little application called “Authy”, it has backups, and provided you remember the backup password, you can install Authy on a new phone, and restore your backup. I also have Authy installed on two phones, one iPhone and one Android phone, and I can use it to get into my account. Then, there are absolutely no issues with problems when losing your phone, since you can just get another one, install Authy, and restore.
Or, also, use a Yubikey, which I also do, which means I can get into my account with either, 2FA code, or Yubikey. If I accidently lose my Yubikey or leave it at home, no problem, I have my phone with Authy.
I find Authy far better than Google Authenticator, because of this ability to restore later.
I also understand that Gitlab don’t want to offer support for free for resetting people’s accounts. And if you don’t want to pay, you can run your own Gitlab server and manage, maintain and support it yourself, and disable 2FA for your user accounts in the Admin panel when your users cannot get into their accounts. I question the reasoning for people who cannot be bothered to run their own server, and yet expect for their 2FA/MFA to be reset for free. If you are unwilling to be burdened with the costs of hosting yourself and managing your own server, why should Gitlab do it for you for free?
So you can run your own server, have the headaches and extra administration tasks. Or, if you want the easy way, stay on Gitlab SAAS with free accounts, and use Authy instead which you can easily restore and get back in when you lose your phone. Then you aren’t locked out of your data.