We construct new examples of solutions of the Hull-Strominger system on non-Kahler torus bundles over K3 surfaces, with the property that the connection del on the tangent bundle is Hermite-Yang-Mills. With this ansatz for the connection del, we show that the existence of solutions reduces to known results about moduli spaces of slope-stable sheaves on a K3 surface, combined with elementary analytical methods. We apply our construction to find the first examples of T-dual solutions of the Hull-Strominger system on compact non-Miller manifolds with different topology.