Gitlab can't clone repository even though ssh works

Try the scp-like syntax:

git clone ssh://[email protected]:1337:project/repository.git

That forces the use of ~/.ssh/config actually, which means the url can be simplified to gitlab:project/repositoriy.git.

But it turned out to be an ssh key issue in the gitlab server ~gitlab/.ssh/authorized_keys (a bit like in issue 4730).
The OP Gelix confirms in the comments:

I removed my key from Gitlab, manually from authorized_keys, readded it on Gitlab. Everything fine now.
Message with SSH Test is now also Welcome to GitLab, Felix *****!

(instead of Welcome to GitLab, Anonymous!)