Puttygen ssh key not accepted by Gitlab EEP

I ran into the same issue as this person (the ticket was not resolved): https://gitlab.com/gitlab-com/support-forum/issues/2631

I am trying to load a new SSH key to my user on Gitlab EEP and the server responds with this message:

Key is invalid
Key type is forbidden. Must be RSA, DSA, ECDSA, or ED25519
Fingerprint cannot be generated"

Steps to reproduce:

  1. Download Puttygen (latest version, 64 bit on Windows 10)
  2. Select the menu option “Key -> SSH-2 RSA Key”
  3. Change the “number of bits in a generated key” from 2048 to 4096
  4. Click on generate
  5. Save the public key and private key

The same for me…