Also met a similar error, caused by a port issue... On a private gitlab instance, default ssh port was changed. I had to add a config file `~/.ssh/config`:
``` Host gitlab.company.com PreferredAuthentications publickey Port 1222 ```

Also met the same error, and in my case it was a port issue... This is configured in my private gitlab instance, where default ssh port was changed. I had to add a config file `~/.ssh/config`:
``` Host gitlab.company.com PreferredAuthentications publickey Port 1222 ```