I think that may actually be more of an issue with how birds work.
See, the reason (many, not all) birds bob their head is because they can't move their eyes, so they have to rely on stabilization of their heads in order to see well. Like with us, we can keep our eyes focused on a thing while birds have to move the entire head.
Because of this, those birds try to keep their heads as static as possible when they move, resulting in the forward-bobbing motion many people associate with them when they have to move the head to keep up with their body.
You can see it here on these pigeons:

In terms of fixing it on the sprite, I'd say quicken the bob so the head juts forward every step they take, like above.