I would attach a control object to the foot's IK handles. That way you can use it to move the feet. You could use a small sphere or a cube or anything you want. Just hide it before you render. Anway. Move the body and keyframe it. Then move the foot's control object and keyframe it.
What I just described is very basic but there is a little more to it . I suggest that you do a search for "inverse foot" rigs. There are plenty of them out there for free! An inverse foot rig is a good way to control each foot.
SimplyMaya specialises in Maya tutorials. We offer over 1,000 individual Maya training videos, ranging from basic Maya tutorials through to intermediate Maya tutorials. Our tutorials are created by instructors with industry experience and are designed to get you up and running in Maya quickly without making it seem like hard work.