絵柄の傾向にもよりますが、素早く処理するならPhotoshopのフィルターにある「ノイズの軽減」または「Camera Rawフィルター」の「ノイズの軽減」を使用すると良いでしょう。

作例を添付しますので比べてみてください。
※Photoshop CCを使用しています。

余談ですが、「tips - GIMPでJPEGの蚊を退治して"PNG"化する」（404 Blog Not Found）を参考に、Photoshopのフィルターで「ぼかし（表面）」も使ってみましたが、手軽な割にはまぁまぁ良い結果が出たので追加して書き込んでおきます。