Cannot add ssh key to my gitlab.com account

When trying to add my ssh key to gitlab.com I get the following error:

  • Fingerprint has already been taken
  • Fingerprint cannot be generated

I was able to use this ssh-key on gitlab.com until yesterday. It stopped working today, so I tried readding it. I only have one gitlab.com account that is linked with my github account. How can I solve this?