Just out of interest how long has it been since your ssh-rsa key was generated?
I would expect it has something to do with this: https://www.openssh.com/txt/release-8.5
Future deprecation notice
It is now possible to perform chosen-prefix attacks against the
SHA-1 algorithm for less than USD$50K.
In the SSH protocol, the “ssh-rsa” signature scheme uses the SHA-1
hash algorithm in conjunction with the RSA public key algorithm.
OpenSSH will disable this signature scheme by default in the near
Note that the deactivation of “ssh-rsa” signatures does not necessarily
require cessation of use for RSA keys. In the SSH protocol, keys may be
capable of signing using multiple algorithms. In particular, “ssh-rsa”
keys are capable of signing using “rsa-sha2-256” (RSA/SHA256),
“rsa-sha2-512” (RSA/SHA512) and “ssh-rsa” (RSA/SHA1). Only the last of
these is being turned off by default.
This algorithm is unfortunately still used widely despite the
existence of better alternatives, being the only remaining public key
signature algorithm specified by the original SSH RFCs that is still
enabled by default.
The better alternatives include:
The RFC8332 RSA SHA-2 signature algorithms rsa-sha2-256/512. These
algorithms have the advantage of using the same key type as
“ssh-rsa” but use the safe SHA-2 hash algorithms. These have been
supported since OpenSSH 7.2 and are already used by default if the
client and server support them.
The RFC8709 ssh-ed25519 signature algorithm. It has been supported
in OpenSSH since release 6.5.
The RFC5656 ECDSA algorithms: ecdsa-sha2-nistp256/384/521. These
have been supported by OpenSSH since release 5.7.
To check whether a server is using the weak ssh-rsa public key
algorithm, for host authentication, try to connect to it after
removing the ssh-rsa algorithm from ssh(1)'s allowed list:
ssh -oHostKeyAlgorithms=-ssh-rsa user@host
If the host key verification fails and no other supported host key
types are available, the server software on that host should be
This release enables the UpdateHostKeys option by default to assist
the client by automatically migrating to better algorithms.
 “SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1 and
Application to the PGP Web of Trust” Leurent, G and Peyrin, T
I was going to check/test find a workaround on Fedora 33 only they still use OpenSSH 8.4p1. Once the Gitlab server is upgraded with an OpenSSH version that supports your client version I expect all will be good.
The other alternative is generate an SSH id-rsa key with SHA2 signature and put this in your gitlab profile, since SSH since 7.3 supports this. Running ssh -vvv firstname.lastname@example.org shows that it runs OpenSSH 7.9 so it will be supported to solve it that way I expect.
Unfortunately OpenSSH 8.5p1 has only just been released so it’s unlikely to be available in most stable distros like Debian/Ubuntu/RHEL for quite some time yet - which means updating the server-side (gitlab.com) isn’t going to happen immediately. And since it’s just been released, other than the info above, there is no other workaround that has been posted yet. Will appear soon I’m sure, this is similar to when DSA keys were deprecated, and from the SSH client, or on the server-side had to add extra parameters to the config to allow it to accept the usage if you didn’t want to generate a new key. I had this and had to move from DSA to RSA keys since DSA then was far less secure apparently.