GItLab doesn't allow me to re-add SSH key

I added an SSH key to my account, then decided I didn’t like the title I had given it so I deleted it and tried to add it again with a different title. But now I always get an error while adding it (regardless of the title):

The form contains the following errors:
Key is too long (maximum is 5000 characters)
Key is invalid
Key type is forbidden. Must be RSA, DSA, ECDSA, or ED25519
Fingerprint has already been taken
Fingerprint cannot be generated

It’s exactly the same key I added successfully before so the only cause I can imagine is “Fingerprint has already been taken”, but seeing that I have deleted the previous key it should be released again I’d say, right?