Same issue. Thanks @nagylzs for creating this topic and thanks to @eworm for sharing the solution. @mt99 That’s a nice tip too!
Here’s the one-liner that I did to automate it in Ubuntu 22.04 and in future Ubuntu versions…
echo "PubkeyAcceptedAlgorithms +ssh-rsa" | sudo tee /etc/ssh/ssh_config.d/rsa-support.conf
No need to restart SSH, as it is a client side configuration.