We derive optimal-order homogenization rates for random nonlinear elliptic PDEs with monotone nonlinearity in the uniformly elliptic case. More precisely, for a random monotone operator on $\mathbb{R}^d$ with stationary law (i.e. spatially homogeneous statistics) and fast decay of correlations on scales larger than the microscale $\varepsilon>0$, we establish homogenization error estimates of the order $\varepsilon$ in case $d\geq 3$, respectively of the order $\varepsilon |\log \varepsilon|^{1/2}$ in case $d=2$. Previous results in nonlinear stochastic homogenization have been limited to a small algebraic rate of convergence $\varepsilon^δ$. We also establish error estimates for the approximation of the homogenized operator by the method of representative volumes of the order $(L/\varepsilon)^{-d/2}$ for a representative volume of size $L$. Our results also hold in the case of systems for which a (small-scale) $C^{1,α}$ regularity theory is available.