Error: GitLab: Your SSH key type is forbidden. Must be RSA, ECDSA, or ED25519

I’ve created a new ssh keypair using the following command - as asked
ssh-keygen -t rsa -C "my_email" -b 4096 -f id_rsa_gitlab.username

Running file command on the created file returns PEM RSA private key

I then did cat on the public key, and pasted on gitlab.com, and saved.

Yet, when I try to push my code, I get

GitLab: Your SSH key type is forbidden. Must be RSA, ECDSA, or ED25519.
fatal: Could not read from remote repository.

This/similar issue has been reported earlier, but was closed as “no updates in few weeks, hence closing”

I also trying creating ecdsa key, yet the same error. (I had to use size 521, cause 4096 was too big for ecdsa)

I think the error is misleading.

Can someone help troubleshoot and fix this issue ?