@piterpasma
Maybe gifsicle can help here. It's pretty good at compression, and I think you can used a reduced amt of colours for this (given the palette):
gifsicle -l0 -k8 --lossy -O3 inputfile.gif > outputfile.gif
The '8' in -k8 tells the amount of colours, you can tweak quality vs size.