Holster your weapon when they appear and use slow motion. Then, use a round house, slide, or bicycle kick when they are close.
Use the following trick in Interval 8, Mission 2 during a Stealth Soldier attack. When you enter the warehouse, kill the first one that is in front of you and let the second one to hit you. Watch it go away, but keep an eye on it. It will come back and jump across the ravine in order to reach you. When it does jump, use slow motion and a round house kick.
Corner yourself so the Stealth Soldiers cannot sneak up behind you. A wall will work, but a corner is better so you have a better view.
A shotgun will works great against any Stealth Soldier.