How to create random variations in speed from multiple duplicated objects all with same walk cycle?

I have a very simple three frame up and down walk cycle created for my monster character. I’ve duplicated the character using Shift-D about a hundred times, and want to make it so they all run across the screen at once. But I would like to create subtle random differences in the timing of they up and down motion to make it look better.

I would also like to randomise the timing of the keyframes where the all end up. I was just going to set keyframes for them all at the start in the Y-axis, then drag them across that axis to the other side and set keyframes there, but would like there to be small variations in the speed they move at.

Is there a way to select random keyframes from multiple objects but all from the same frame? Or is there a better way to do what I’m trying to do?