What "loses energy" actually means here depends on what kind of redshift you're talking about.

If you're talking about gravitational redshift, because the light is climbing out of the gravity well of a planet or star, there actually is a conserved energy involved--but it's not the one you're thinking of. In this case, there is a time translation symmetry involved (at least if we consider the planet or star to be an isolated system), and the associated conserved energy, from Noether's Theorem, is called "energy at infinity". But, as the name implies, only an observer at rest at infinity will actually measure the light's energy to be that value. An observer at rest at a finite altitude will measure a different value, which decreases with altitude (and approaches the energy at infinity as a limit). So when we say the light "redshifts" in climbing out of the gravity well, what we actually mean is that observers at higher altitudes measure its energy (or frequency) to be lower. In other words, the "energy" that changes with altitude isn't a property of the light alone; it's a property of the interaction of the light with the observer and their measuring device.

If you're talking about cosmological redshifts, due to the expansion of the universe, here there's no time translation symmetry involved and therefore Noether's Theorem doesn't apply and there is indeed no conserved energy at all. But even in this case, the redshift is not a property of the light alone; it's a property of the interaction of the light with a particular reference class of observers (the "comoving" observers who always see the universe as homogeneous and isotropic).

Where does the energy go then?

Edit: I just looked into this & there are a few explanations for what is going on. Both general relativity & quantum mechanics are incomplete theories but there are several explanations that account for the seeming losses that seem reasonable to me.