Nods and shrugs and the like are hardly useless. You don't need to eliminate them entirely. You just want to use them strategically as a small part of your dialogue support. Include actions, expressions, gestures, sensory observations, internal reactions, all of that stuff, but keep them all minimal. Use them to flesh out your scene and make it immersive. Use them to fine-tune the cadence of dialogue. And when it makes sense, use them instead of dialogue, but again, all in moderation.
Also remember that some characters are going to be more animated, moving around more, speaking with their hands, etc., while others will be verbose but stationary, and still others will be more stoic or contemplative and likely to nod instead of answering verbally. The amount of physicality you give a scene should depend partially on the characters and what they're feeling in the moment.