I’m a music and movement specialist teacher by training.
The first step in learning to count is to develop beat bonding. Walking to music with a strong steady beat, and then adding something (a jump, a clap, etc) on specific beats works well. The goal is to be able to continue that internal beat without music or anyone counting, but keep it steady. A lot of beat bonding could be integrated into conditioning, and you could work on that while also working on the routine. If your kids have a good school music program, they may already have those skills solidly.