I am having the same problem.

in .IntelliJIdea2019.2/system/log/idea.log I see

2019-09-22 13:43:58,474 [649136973]   WARN - z.sshj.transport.TransportImpl - Dying because - Unable to reach a settlement: [ssh-dss] and [rsa-sha2-512, rsa-sha2-256, ssh-rsa, ssh-ed25519] 
net.schmizz.sshj.transport.TransportException: Unable to reach a settlement: [ssh-dss] and [rsa-sha2-512, rsa-sha2-256, ssh-rsa, ssh-ed25519]
    at net.schmizz.sshj.transport.Proposal.firstMatch(Proposal.java:145)
    at net.schmizz.sshj.transport.Proposal.negotiate(Proposal.java:129)
    at net.schmizz.sshj.transport.KeyExchanger.gotKexInit(KeyExchanger.java:224)
    at net.schmizz.sshj.transport.KeyExchanger.handle(KeyExchanger.java:356)
    at net.schmizz.sshj.transport.TransportImpl.handle(TransportImpl.java:503)
    at net.schmizz.sshj.transport.Decoder.decodeMte(Decoder.java:159)
    at net.schmizz.sshj.transport.Decoder.decode(Decoder.java:79)
    at net.schmizz.sshj.transport.Decoder.received(Decoder.java:231)
    at net.schmizz.sshj.transport.Reader.run(Reader.java:59)

Apparently, this is because the client offer of [ssh-dss] and the server list [rsa-sha2-512, rsa-sha2-256, ssh-rsa, ssh-ed25519] don't intersect, so the protocol cannot agree on a mutually supported algorithm for ssh.

There are various related issues on https://github.com/hierynomus/sshj as well as https://stackoverflow.com/questions/30846076/jsch-algorithm-negotiation-fail.

So far, I did not have any luck fixing this.

I am having the same problem.

in .IntelliJIdea2019.2/system/log/idea.log I see

2019-09-22 13:43:58,474 [649136973]   WARN - z.sshj.transport.TransportImpl - Dying because - Unable to reach a settlement: [ssh-dss] and [rsa-sha2-512, rsa-sha2-256, ssh-rsa, ssh-ed25519] 
net.schmizz.sshj.transport.TransportException: Unable to reach a settlement: [ssh-dss] and [rsa-sha2-512, rsa-sha2-256, ssh-rsa, ssh-ed25519]
    at net.schmizz.sshj.transport.Proposal.firstMatch(Proposal.java:145)
    at net.schmizz.sshj.transport.Proposal.negotiate(Proposal.java:129)
    at net.schmizz.sshj.transport.KeyExchanger.gotKexInit(KeyExchanger.java:224)
    at net.schmizz.sshj.transport.KeyExchanger.handle(KeyExchanger.java:356)
    at net.schmizz.sshj.transport.TransportImpl.handle(TransportImpl.java:503)
    at net.schmizz.sshj.transport.Decoder.decodeMte(Decoder.java:159)
    at net.schmizz.sshj.transport.Decoder.decode(Decoder.java:79)
    at net.schmizz.sshj.transport.Decoder.received(Decoder.java:231)
    at net.schmizz.sshj.transport.Reader.run(Reader.java:59)

Apparently, this is because the client offer of [ssh-dss] and the server list [rsa-sha2-512, rsa-sha2-256, ssh-rsa, ssh-ed25519] don't intersect, so the protocol cannot agree on a mutually supported algorithm for ssh.

I followed the advice at https://intellij-support.jetbrains.com/hc/en-us/community/posts/360004370099-DataGrip-2019-2-RC-SSH-Tunnelling-no-longer-works to resolve this issue.

First, I found that I have the following in /etc/ssh/ssh_config

# Custom options from `extraConfig`, to override generated options


# Generated options from other settings
Host *
AddressFamily any

XAuthLocation /nix/store/mpa2k8as7sympa93rzvrvkmhrh6pnahi-xauth-1.0.10/bin/xauth


ForwardX11 no

PubkeyAcceptedKeyTypes +ssh-dss
HostKeyAlgorithms +ssh-dss

Then I added the following to ~/.ssh/config

Host *
    HostKeyAlgorithms rsa-sha2-512,rsa-sha2-256,ssh-rsa,ssh-ed25519

This fixed my problem.