The old one at least looks like he's walking, the new one makes it look like he's flailing/kicking his way around. The reason this is is because of that hind leg. Even though the depth is there, the contours of that leg are similar enough to his right leg when it goes back, too much. This causes our eyes to merge the two legs and confuse them, whereas they should both be readable.
The old animation looks like he has some weight to him, which fits for the heavy gear/underwater environment. But if you want to fix that new sprite, I would suggest using the foot at 90 degrees for the hind leg, and more flat, less angled foot for the front leg. You could also experiment with the foot angles of the front leg when it kicks forward, to make sure there is a balance. And yeah if you can do more than 3 frames, then do it for the sake of fluidity.
