I deleted my local Gitlab repository (using Ubuntu) and recreated it. Now I wanted to add a new SSH key so I don't have to type email/pw on every push. What I did:
ssh-keygen -t rsa -b 4096 -C "my@email.com"
ssh-add ~/.ssh/id_rsa
Then added the content of id_rsa.pub into the key form on Gitlab/SSH Keys. I deleted every old key in the settings and also every key in ~/.ssh/ before. And i still get the messages:
Fingerprint has already been taken / Fingerprint cannot be generated