There are several ways of solving this problem; different shoes is certainly one way.
I recommend shoes such as

These are really designed for Mountain Biking. Like any bike shoe they have a stiff sole, which helps with keeping your feet on the pedals, and stops you hurting the arches of your feet, which can occur with ordinary runners / tennis shoes / sports shoes. The rugged grip pattern also helps the shoes grip the pedals.
A key advantage of such shoes is that they are ready for when you want to change pedals to so called "Clipless" pedals (which you actually clip into). When and if you take that step, you will have completely solved the "foot retention" problem. These shoes have a section in the sole that will accommodate SPD pedal cleats. You can use them without cleats though.
The picture comes from an Australian website, but I'd expect you can get them or something similar where you are.
I have worn an older version of these shoes for 5 years.