In the last few days, I've started getting this message when connecting with SSH from Ubuntu 22.04 to Oracle Linux 8 systems.
Fix: ssh -c aes256-gcm@openssh.com user@host
Presumably either Ubuntu or Oracle Linux (and possibly RedHat) has messed up a patch for the default cipher (apparently chacha20-poly1305@openssh.com) for that combination of operating systems. But selecting aes256-gcm works around the problem.
This probably relates to early fixes for the Terrapin vulnerabilities.
UPDATE... If I merely disable cipher chacha20-poly1305@openssh.com then the two ends negotiate cipher: aes128-ctr with MAC: umac-128-etm@openssh.com , and I get a different error:
ssh_dispatch_run_fatal: Connection to x.x.x.x port 22: message authentication code incorrect
So for now perhaps the easiest thing is to enable just cipher aes256-gcm@openssh.com in /etc/ssh/ssh_config whilst we wait for more mature fixes for Terrapin. I'm reluctant to go forcing just one cipher on the server side, in case I lock myself out of a box.