En latex, du moins si on veut compiler en pdf, il est conseillé d'utiliser des images au format eps.
Il existe un outil très bien, ImageMagick, qui peut être utilisé dans ce cas, notamment dans convert.

#! /bin/bash

for i in *.gif; do
  convert $i ${i%gif}eps ;
done

Ce mini script permet de convertir tous les gifs en eps, il suffit de remplacer gif par jpg pour changer de source.
Voila, dites moi si vous avez des optimisations.