Gitlab.com does not accept ssh keys, resulting in "Permission denied"

Wow!
Using ‘git’ as the user instead of my own user name did the trick!

$ ssh -T git@gitlab.com
Welcome to GitLab, @matthias_muth!

Thanks a lot, bartj!