How do I avoid Keynote reducing image quality?
After some research I found that this is a problem that has appeared since Keynote 6, and is probably due to iOS compatibility (limiting PNG original quality to stick up to 4096px height).

A tip however was to import your image as PDF instead, then Keynote won't downsample it. 

Here's the result: