「メディアキャッシュファイルを削除」がすごく遅くなりました。。

キャッシュの保存場所については、理想的には高速なSSDなどをキャッシュ専用に用意するということにはなると思うのですが、編集作業用ファイル一式を保存している外付けSSDにキャッシュの保存場所を用意することも間違いではなく、むしろその方法をおススメしている方もいらっしゃいます。

（私の場合は、デスクトップ機ではNVMe接続のSSDを2つマザーボードにのせて、片方をOS起動・アプリインストールのCドライブ、もう片方をメディアキャッシュとAfter Effectsのデスクキャッシュ用のDドライブに設定して使用しています。MacBook Proでは、デフォルト設定のまま起動ディスク上にキャッシュを保存しています。）

ご参考URL

Premiere Pro および After Effects の推奨ハードウェア 

キャッシュの削除時間はキャッシュファイルの数や容量にも影響されるかと思うのですが、さすがに1分以内と20分では差がありすぎるように思います。

Premiere ProはまだmacOS Sonomaに正式には対応していない（2023/11/3時点での情報です。macOS 14 Sonoma でアドビアプリを実行できますか？ ）ことも気になる部分ではございますが、macOSのアクティビティモニターでキャッシュ削除中のディスクの動作の様子をご確認いただくことで、なにかヒントが得られるかもしれないようにも思います。