For a high-dimensional problem, a randomized Gram-Schmidt (RGS) algorithm is beneficial in terms of both computational cost and numerical stability. We apply this dimension reduction technique by random sketching to Krylov subspace methods, e.g., to the generalized minimal residual method (GMRES). We propose a flexible variant of GMRES with the randomized Gram-Schmidt-based Arnoldi iteration to produce a set of basis vectors of the Krylov subspace. Even though the Krylov basis is no longer $\ell_2$-orthonormal, its random projection onto the low-dimensional space achieves $\ell_2$-orthogonality. As a result, the numerical stability is observed, which turns out to be independent of the dimension of the problem, even in extreme-scale problems.On the other hand, as the harmonic Ritz values are commonly used in GMRES with deflated restarting to improve convergence, we consider another deflation strategy—for instance, disregarding the singular vectors associated with the smallest singular values. We thus introduce a new algorithm: randomized flexible GMRES with singular value decomposition (SVD)-based deflated restarting. At the end, we carry out numerical experiments in the context of compressible turbulent flow simulations. Our proposed approach exhibits quite competitive numerical behavior compared to existing methods while reducing computational costs.