I want to know if the hundreds of songs I downloaded in the past on an old device that was stolen or broken can be recovered somehow? do I have really have to download all that again?
You may hope to recover something from a broken device you still have access to, nevertheless it depends on the kind of malfunction or damage. Anyway, it wouldn't be probably worth the effort.
But I cannot even imagine a way to retrieve some songs from a stolen device that would be easier and faster than merely having them downloaded again.