Two-Factor Authentication issue

Hi all!
How can I authenticaticate to gitlab without recovery codes?
I lost them and lost my laptop also. and now when I’m trying to generate new ones I have an error. > git@gitlab.com: Permission denied (publickey).
As I understood it’s because it’s new laptop and new public key.

what I should to do for fixing it?

Thank you