1 - Make a duplicate of your original Keynote
2 - Right Click on the Duplicate of your Keynote and view the package contents.
3- Open the folder called “Data” and remove your embedded videos contained within it by moving them to another location or folder like your desktop.
4 - Re-encode your videos using “Handbreak.app” with similar format settings but outputting them with “Fast 1080p30” with video encoder set to “MPEG-4”
5 - Open the duplicate keynote file in keynote app. It should say the movies embedded are corrupt.
6 - Replace the media now in the document with your new re-encoded videos.
7 - Now export from keynote again and your new movie will look a lot better.