Experimental spin relaxation times in graphene, critical for spintronics and quantum information technologies, are two orders of magnitude below previous theoretical predictions for spin-phonon relaxation. Here, ab initio density-matrix dynamics simulations reveal that electric fields and substrates strongly reduce spin-phonon relaxation time to the nanosecond scale, in agreement with experiments. Our predicted out-of-plane to in-plane lifetime ratio exceeds 1/2 on boron nitride substrates, matching experiment unlike previous models, suggesting that spin-phonon relaxation is dominant in graphene at room temperature.