SSH to gitlab server not working: ssh_dispatch_run_fatal: incorrect signature eror

I upgraded machine to latest Ubuntu 20.04 and the machine is now unable to connect using SSH to existing, unchanged gitlab server. The used keys and credentials are the same as before. Originaly I wanted to git clone the repo, but then tried just ssh to the server and the result is the same: incorrect signature error.

Partial (full log was marked as spam) log on command ssh -vvv is:

openSSH_8.2p1 Ubuntu-4, OpenSSL 1.1.1d 10 Sep 2019
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: include /etc/ssh/ssh_config.d/*.conf matched no files
debug1: /etc/ssh/ssh_config line 21: Applying options for *
debug2: resolving "serveraddr.com" port 22
debug2: ssh_connect_direct
debug1: Connecting to serveraddr.com [10.0.0.xxx] port 22.
debug1: Connection established.
...
debug1: Local version string SSH-2.0-OpenSSH_8.2p1 Ubuntu-4
debug1: Remote protocol version 2.0, remote software version OpenSSH_7.4p1 Debian-10+deb9u5
debug1: match: OpenSSH_7.4p1 Debian-10+deb9u5 pat OpenSSH_7.0*,OpenSSH_7.1*,OpenSSH_7.2*,OpenSSH_7.3*,OpenSSH_7.4*,OpenSSH_7.5*,OpenSSH_7.6*,OpenSSH_7.7* compat 0x04000002
debug2: fd 3 setting O_NONBLOCK
...
debug1: Host 'serveraddr.com' is known and matches the ECDSA host key.
debug1: Found key in /home/username/.ssh/known_hosts:1
ssh_dispatch_run_fatal: Connection to 10.0.0.xxx port 22: incorrect signature

There is probably some misconfiguration between client and server (also openssh version is different), but I am unable to find out what specifically.

1 Answer

I was finally able to connect by adding line HostKeyAlgorithms ssh-rsa to /etc/ssh/ssh_config. The git clone command is now also working.

It would be great if someone could explain what exactly is happening, because nothing in the ssh log points me to this. Full log available on pastebin, because here it was marked as spam: