private メソッドをテストすべきかどうかは色々意見がありますが、あるクラスの private メソッドの割合が、public メソッドに比べて非常に多くなった場合は、private メソッドのテストも書きたくなるかもしれません。
そのような場合は、クラス抽出のリファクタリングを考えるとよいです。 特定の処理がクラスとして抽出されれば、そのクラスを利用するインタフェースは public メソッドになるので、自然にテストを記述できるようになります。 もとのクラスの見通しもよくなり、一石二鳥です。
計算処理を担うようなメソッドはテストを記述するよい対象になりますが、private メソッドのままではテストが記述できません。 そのような場合は、public static なユーティリティメソッドに変更することで、テストを記述できるようにするとよいです。 そのメソッド内でフィールドにアクセスしないユーティリティメソッドになっていれば（ステートレス）、オブジェクトに副作用を与えることはないので、public メソッドにしても悪影響は出ません（カプセル化は崩れない）。
JxUnit のように private メソッドをテスト可能なフレームワークを使用するのもひとつの手です。 JxUnit は内部でリフレクションを利用して private メソッドのテストを可能にしています。