Podrias hacerlo con paint o photoshop pero saldiran resultados muy burdos.
Seria cuestion de habilidad, quitando niveles inecesarios de pixeles, sacrificando una parte inecesaria del sprite para ahorrar espacio, tambien podrias "achicar" alguna parte como las alas del murcielaguito ese xD, aprende intentando ;D.
P.D. Ultimamente habia reedimensioando el golem ese:
Espero que no infinja normas :D