In this Letter we demonstrate a fundamentally new, to the best of our knowledge, concept to enhance the magnetic modulation of the surface plasmon polaritons (SPPs) by using hybrid magneto-plasmonic structures consisting of hyperbolic plasmonic metasurfaces and magnetic dielectric substrates. Our results show that the magnetic modulation of SPPs in the proposed structures can be an order of magnitude stronger than in the hybrid metal-ferromagnet multilayer structures conventionally used in active magneto-plasmonics. We believe that this effect will allow for the further miniaturization of magneto-plasmonic devices.