Anti-aliaing isn't a bad thing (when done in a controlled way) and has nothing to do with the opacity effect you're using. The large amount of automatically generated colours your opacity effect creates are the issue.

You could go through each frame and fine-tune the colours  to reuse a smaller number of colours.

If you want to spend more time on this piece, you could go the extra mile and hand-animate the transition so that instead of fading in, the creature actually comes out of the darkness (the shadows on it would change, etc). It would be a lot more work but it'd look really awesome, I think.

(Also, I recommend linking gifs rather than gifv when dealing with pixel art. Video is lossy, the formats are designed for gifs made of videos and such, not for pixel art.)