PNG is fine for this. A palletized PNG on max compression would be smaller than the game and totally lossless unlike this. First you gotta take this image and map/quantize it to the original palette though to destroy the JPEG artifacts, which produce colors in between ones that would have existed in the game's output.