You had so much bounce in your first version. What happened?
Try making it so when he steps off his foot he pushes up quickly to highest height, then holds for a frame then drops down just before he pushes off with the next foot. Then play around with smoothing that out a little but make the push off the foot the most sudden change.
Once you have this movement right, it should be easy to animate the air based on this bouncing movement.
The belt tail looks too stiff.
You could make it flow like in curves like waves instead so it looks like cloth.
Again, I think let the waves flow from the body movement for best effect.
Also slow down the idle animation. Even if he is breathing heavily from running alot, he would hyperventilate from breathing that fast
Again the belt tail sticks out strangely instead of hanging down.