We report a high efficiency Brillouin random fiber laser (BRFL) enabled by a random fiber grating (RFG) with demonstration of replica symmetry breaking (RSB). The RFG was characterized by optical coherence tomography (OCT) method, which measured the spatially resolved reflectivity of RFG by a tunable delay line. Multiple narrow linewidth peaks appeared in reflection spectrum of RFG, created by frozen scattering centers acting as narrow linewidth filters to select random modes in random fiber lasers based on Brillouin gain. With the scattering from RFG as disordered feedback, a BRFL with slope efficiency of 29.3% and lasing threshold of 10.2 mW was demonstrated with 1 kHz linewidth. Intensity dynamics show that RFG can reduce the noise of BRFL with a symmetric phase portrait, indicating the increased mean path length and coherence time of the Stokes photons. The probability distribution of the Parisi overlap parameter of intensity fluctuation spectra from trace to trace reveal a photonic spin-glass phase with RSB in the RFG enabled BRFL, providing a photonic platform to study the photon glassy behavior of random fiber lasers.