I just tried reducing the size of a sprite in Paint and it works just fine. But to reiterate, you must refine the sprite meaning you will have to clean up the sprite and that considers you have some knowledge of pixel art in order to bring the quality up to par.
To make this easier:
Here is Gardevoir BEFORE re-sizing 96x96:
Here is Gardevoir AFTER resizing to 64x64:
As you can see the quality still sucks. So you're gonna have to refine it like I did here really quick: