ssh-keygen -t rsa を今でも打っているなら、この記事は読む価値があります。ここ数年でOpenSSH側の推奨がかなり動いていて、昔の手順書のままだと接続すらできない場面が出てきました。
1. ssh-rsa はもう繋がらない

古いRSA鍵、正確には ssh-rsa という署名方式はSHA-1を使っています。SHA-1の衝突が現実的になって久しく、OpenSSH 8.8(2021年)でデフォルト無効になりました。
古い機器に繋ごうとしてこれを見たことがある人は多いはずです。
Unable to negotiate with ...: no matching host key type found. Their offer: ssh-rsa
サーバー側が壊れたわけではなく、クライアントが ssh-rsa を受け付けなくなっただけです。急ぎなら -o HostKeyAlgorithms=+ssh-rsa で通りますが、通るだけで何も安全になっていません。鍵長ではなく署名方式の問題なので、RSAを使い続けるなら両端が rsa-sha2-256 や rsa-sha2-512 に対応している必要があります。
2. 迷ったら Ed25519
2048か4096かで悩む時代は終わりました。今は Ed25519 を選べば済みます。
ssh-keygen -t ed25519 -C "your-email@example.com"
鍵長を選ばなくていい、というのが個人的には一番ありがたい点です。公開鍵が一行に収まるので authorized_keys を目で追えますし、署名も速い。RSA 4096との差は日常操作では体感しづらいものの、CIで何百回も認証するような場面では効いてきます。
例外は、相手側が古すぎて Ed25519 を知らないケース。組み込み機器や古いネットワーク機器では今でも遭遇します。
3. FIDO2 セキュリティキー
OpenSSH 8.2 から、YubiKey などの FIDO2 デバイスが追加ソフトなしで使えるようになりました。
ssh-keygen -t ed25519-sk
ディスク上に置かれるのは「鍵ハンドル」と呼ばれる参照情報だけで、秘密鍵そのものはデバイスから出てきません。ノートPCを盗まれてもマルウェアを踏んでも、物理キーが手元にある限りサーバーには入れない状態を作れます。
接続のたびにキーに触る必要があるのは面倒ですが、そのおかげでスクリプトが勝手に踏み台を越えていく事故が起きません。裏を返せば、cronやCIから使う鍵には向いていないということです。
-O resident を付けるとデバイス内に鍵情報ごと保存され、別のPCからでも ssh-keygen -K で取り出せます。持ち歩く前提ならこちらです。
4. Windows でも素で使える
Windows 10/11 には OpenSSH クライアントが標準で入っていて、PowerShell からそのまま ssh が叩けます。サーバー側もオプション機能として追加できます。PuTTY の出番はシリアル接続とセッション管理くらいまで減りました。
ひとつ落とし穴があって、OpenSSH Authentication Agent サービスは既定で無効です。ssh-agent を使うなら手動で有効化してください。
結局どれを使うか
ssh-rsa と ssh-dss は捨てる。DSAに至っては OpenSSH 10 で完全に削除されました。普段使いは ed25519、落としたくないサーバーは ed25519-sk に寄せる。ひとまずこれだけで十分です。