VPSへのSSH接続、Permission denied (publickey)たまに出ますよね。。
久々VPSへの接続するぞって時にこのエラーが出て結構ストレスになっています。
最近、以下の方法でエラーが解消できたので参考程度に見ていただければと思います。

自分の環境

PC：MacBookAir （M1チップ、Bigsur)
VPS：さくらVPS
接続方法：SSH接続（ノーパスワード）

方法1.パーミッションの確認

これはエラー名でググるとだいたい出てくる対処法のため、試していると思いますが念のため。。
キーとキーが保存されているディレクトリの権限確認です。
参考URL：ssh接続でPermission deniedと表示されたときの対処法

方法2.SSH AGENTへの秘密鍵の登録

僕は上記方法でダメだったので、秘密鍵の発行と登録はできているけど、接続時に秘密鍵がうまくサーバに渡せていないのではないか？ということを疑いました。
そこで登録した秘密鍵を必要な時に取り出してくれるSSH AGENTで秘密鍵の登録状況を調べ、秘密鍵を登録しました。僕はこれでVPSへのSSH接続がなおりました。

まず、以下コマンドで情報を確認します。
(以下はMacターミナルで実行します）

ssh-add -l
#=> コマンドの結果として僕の場合は以下が表示されました
The agent has no identities.

特に何も登録がされていないようなので、登録を実行

ssh-add ~/.ssh/client_rsa
#=> client_rsaは、rsa鍵ファイルでrsa鍵に別名をつけている場合はこのファイル名に限りません

以下コマンドで登録状態を再確認。

ssh-add -l
#=> コマンドの結果として僕の場合は以下が表示されました
2048 ****（文字列が続く）

登録ができていることを確認できたので、VPSへSSH接続を試す。
⇨接続できた

方法3.秘密鍵の再発行

一番確実な方法かもしれません。。（僕も何回もお世話になりました）
参考にしているURLを貼ります。
ssh-add ~/.ssh/client_rsa

番外編　Connection refused(接続拒否）エラーが発生した場合の対処法

これは今回のとは別エラーですが、もし出た時に解消する参考になるかもと思い、蛇足ですが載せておきます。
（ただ、根本的な解決にはいたっていません。。）
・確認
サーバーに対してネットワーク経路が確保できているか確認する。

ping サーバIPアドレス
#=> 自分の場合はtimeoutが発生

・解決方法
別のネットワークで接続してみる。
⇨自分の場合はスマホのデザリングからポケットwifiに切り替えることで解消

以上です。

何かのお役に立てれば幸いです。