We reveal a phase transition with decreasing viscosity in one-dimensional decaying Burgers turbulence with a power-law correlated random profile of Gaussian-distributed initial velocities. The low-viscosity phase exhibits non-Gaussian one-point probability density of velocities reflecting a spontaneous one step replica symmetry breaking in the associated statistical mechanics problem. We obtain the low orders cumulants analytically. Our results, which are checked numerically, are based on combining insights in the mechanism of the freezing transition in random logarithmic potentials with an extension of duality relations discovered recently in Random Matrix Theory. (Based on the joint work with Pierre Le Doussal and Alberto Rosso.)