We prove that any continuous and convex stationary ergodic Hamiltonian admits critical subsolutions, which are strict outside the random Aubry set. They make up, in addition, a dense subset of all critical subsolutions with respect to a suitable metric. If the Hamiltonian is additionally assumed of Tonelli type, then there exist strict subsolutions of class $\CC^{1,1}$ in $\R^N$. The proofs are based on the use of Lax--Oleinik semigroups and their regularizing properties in the stationary ergodic environment, as well as on a generalized notion of Aubry set.