First make your random footstep cue. Then open up the walking animation and look for notify section. Right click on the notify section and add sound and adjust it to the animation for when you want it to play along with the animation.
In your case as soon as the foot hit the ground frame.