We propose a new physically-based ``multifractal stress activation model of earthquake interaction and triggering based on two simple ingredients: (i) a seismic rupture results from activated processes giving an exponential dependence on the local stress; (ii) the stress relaxation has a long memory. The combination of these two effects predicts in a rather general way that seismic decay rates after mainshocks follow the Omori law 1/t^p with exponents p linearly increasing with the magnitude M of the mainshock and the inverse temperature. We carefully test the prediction on the magnitude dependence of p by a detailed analysis of earthquake sequences in the Southern California Earthquake catalog. We find power law relaxations of seismic sequences triggered by mainshocks with exponents p increasing with the mainshock magnitude by approximately 0.1-0.15 for each magnitude unit increase, from p(M=3) approx 0.6 to p(M=7) approx 1.1, in good agreement with the prediction of the multifractal model. The results are robust with respect to different time intervals, magnitude ranges and declustering methods. When applied to synthetic catalogs generated by the ETAS (Epidemic-Type Aftershock Sequence) model constituting a strong null hypothesis with built-in magnitude-independent $p$-values, our procedure recovers the correct magnitude-independent p-values. Our analysis thus suggests that a new important fact of seismicity has been unearthed. We discuss alternative interpretations of the data and describe other predictions of the model.