> 画像をGIFにしようと、イメージレディで減色しているのですが、どうしても8k以下になりません。6.7k以下にしなければなりません。

Phoshop 6.01をお持ちであれば、Web用に保存でフォーマットをGIF、
ファイルサイズの最適化で6.7kに設定してやればある程度のクオリティで
そのサイズに近いものに変換できます。あとは自分で微調整をしてみてはい
かがでしょう。

> できるだけ劣化を押さえつつ減色する最適な方法はどうすればよいのでしょうか？

手作業でビット１つずつを直していくしかありません。