We study theoretically the relaxation of quasi-particle spins in graphene in proximity to an s-wave superconductor in the presence of resonant magnetic and spin-orbit active impurities. It is well known that off resonance, the relaxation behaves as predicted from superconducting coherence: with lower temperatures the spin relaxation increases when electrons scatter off magnetic impurities (Hebel-Slichter effect), and decreases when the scatterers act via spin-orbit coupling. This distinct temperature dependence, not available in the normal state, can uniquely discriminate between the two scattering mechanisms. We have shown [1] that the Hebel-Slichter picture breaks down when magnetic impurities act resonantly—the emergent Yu-Shiba-Rusinov states inside the gap shift the spectral weight of the magnetic resonances and thus suppress their interaction with quasi-particle states. As a consequence this leads to a significant decrease of the spin-relaxation rate at lower temperatures. Our findings are valid for generic s-wave superconductors that host resonant magnetic impurities.