Achieving robust legged locomotion on complex terrains poses challenges due to the high uncertainty in robot-environment interactions. Recent advances in bipedal and quadrupedal robots demonstrate good mobility on rugged terrains but rely heavily on sensors for stability due to low static stability from a high center of mass and a narrow base of support. We hypothesize that a multi-legged robotic system can leverage morphological redundancy from additional legs to minimize sensing requirements when traversing challenging terrains. Studies suggest that a multi-legged system with sufficient legs can reliably navigate noisy landscapes without sensing and control, albeit at a low speed of up to 0.1 body lengths per cycle (BLC). However, the control framework to enhance speed on challenging terrains remains underexplored due to the complex environmental interactions, making it difficult to identify the key parameters to control in these high-degree-of-freedom systems. Here, we present a bio-inspired vertical body undulation wave as a novel approach to mitigate environmental disturbances affecting robot speed, supported by experiments and probabilistic models. Finally, we introduce a control framework which monitors foot-ground contact patterns on rugose landscapes using binary foot-ground contact sensors to estimate terrain rugosity. The controller adjusts the vertical body wave based on the deviation of the limb's averaged actual-to-ideal foot-ground contact ratio, achieving a significant enhancement of up to 0.235 BLC on rugose laboratory terrain. We observed a $\sim$ 50\% increase in speed and a $\sim$ 40\% reduction in speed variance compared to the open-loop controller. Additionally, the controller operates in complex terrains outside the lab, including pine straw, robot-sized rocks, mud, and leaves.