古い環境のrailsアプリをcapistranoでビルドしようとしたところ、以下のエラーになった。

cap aborted!
Net::SSH::Exception: could not settle on host_key algorithm

おそらくopensslがデフォルトでRSAをサポートしなくなったことが原因。単純なSSH接続の場合はこの方法で解決できました。
今回はどうやらcapistranoが使っているnet-sshが古すぎて +ssh-rsa という記法を理解できなくて、+ssh-rsa を追記してもcapistranoが失敗してしまうという状況。

以下のように対応するアルゴリズムをすべて列挙し解決しました。
本来ならサーバーの公開鍵を差し替えるのが正しいと思いますが、とりあえずワークアラウンドとして。

Host * 
   #PubkeyAcceptedKeyTypes=+ssh-rsa 
   #HostKeyAlgorithms=+ssh-rsa 
+ # +記法に対応していない古いruby net-sshのため 
+ HostkeyAlgorithms=ssh-ed25519,ssh-rsa,rsa-sha2-256,rsa-sha2-512,ssh-dss,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521 
+ # +記法に対応していない古いruby net-sshのため 
+ keyAcceptedKeyTypes=ssh-ed25519,ssh-rsa,rsa-sha2-256,rsa-sha2-512,ssh-dss,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521