sshの設定が上手く言っているか試す

$ ssh -T git@gitlab.com

成功した場合

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

失敗した場合

$ ssh -T git@gitlab.com
The authenticity of host 'gitlab.com (104.210.2.228)' can't be established.

失敗した場合の対策
gitlab の profile から ssh key がちゃんと登録されているか確認する。SSH をはじめに使う場合、鍵が何個も登録されている場合はとりあえず使う奴に絞って、後は remove しとく。何個も登録されてると、違う鍵になってたりする。あと回線がhttpsしか許可されてない場合とかも稀によくあるかもしれない。

ssh -vT git@gitlab.com

でデバッグできるらしい。-T のオプションは使っていない人も多いみたいなのでつけないと駄目って事もないと思う。