You're coming at this problem from the wrong angle. Any size is fine as long as the scale is consistent.
If you're making a game I would suggest deciding how big your player character is. It's true that the bigger a size you pick for your character, the more detail you can give them. What you are balancing against though, is the size of the player's vision on the screen. If you've ever played the old donkey kong games for GBC, their sprites took up 10% of the screen which made it hard to know what was coming when moving around.
Then that's your reference, and everything from there is scaled based on your reference. The size of your initial reference is mostly a style thing. You can have lots of detail or simplicity in both large and small sprites.
As for your sprite, you could definitely make that smaller and still show all the detail you currently have. There is however, nothing wrong with it's size as it is, unless your player is going to be 5 or 6 times as tall and you don't want your player to be half as tall as the screen. Then again that size could work if your game is a side-scroller with not much vertical movement. (back and forth all day, the world is your oyster)
EDIT:
I made a 32x32 based on your sprite. Looks a bit different but what can you do?
