I experienced the issue described here, and wanted to share my solution, but the issue is closed for comments (although the youtrack there refers to a different issue).
I was getting "USERAUTH FAIL" (and not "Algorithm negotiation fail" that is addressed in the youtrack).
The problem appears to be in the ssh key I had used. While it didn't have a passphrase, it seems that it was encrypted. Apparently OpenSSH doesn't like that.
I could tell that it's encrypted by the header:
-----BEGIN RSA PRIVATE KEY-----
I replaced the key with an unencrypted one, and now everything works.