GitLab: “Permission Denied (publickey)” after properly uploading your public key?

If this shows you a nice “Welcome!” message, everything is fine:

$ ssh -T git@gitlab.com

https://forum.gitlab.com/t/permission-denied-publickey/29670

Quite likely you SSH agent does not have you corresponding private key yet. Go and add it!