This is a very nice start, the legs are working nicely

.
The thing I always do for cyclical animation is isolate the parts where the arcs are most important (Hands/ Feet/ Shoulders/Hips and Head) and animate them individually, paying as much attention as I can to ease in and out and keeping very smooth arcs. Actually draw the arcs on another layer if it helps (
example). The biggest issue with this animation is jitter, the hands in particular move at an uneven rate, they should act like pendulums (see previous example). Try dragging the hands as well. The cycle on the head movement is a bit strange also, while it can look nice to have the character thrust forward a bit with each step the head should follow a circular arc, not just side to side.
I'm not sure how familiar you are with animation terminology so just shout if you need me to explain anything.