Ssh_dispatch_run_fatal no cipher error with multiple keys

How to Use GitLab
1

I can’t clone nor pull from repositories at gitlab. I’m getting the error

ssh_dispatch_run_fatal: Connection to 104.210.2.228: no matching cipher found
fatal: Could not read from remote repository.

Please make sure you have the correct access rights
and the repository exists.

I tried creating a new key and deploying it, thinking that git wasn’t detecting the previous one properly. But I get the same error.

I’m in Ubuntu, and this info may be relevant. Let me know if you need something else.

$ lsb_release -a
Distributor ID:    Ubuntu
Description:    Ubuntu 15.10
Release:    15.10
Codename:    wily

$ git --version
git version 2.5.0

$ ssh -v localhost
OpenSSH_6.9p1 Ubuntu-2ubuntu0.2, OpenSSL 1.0.2d 9 Jul 2015