What country are you in ? If you are in a country where music can be redownloaded then you should be able to redownload it via the Purchased tab in the iTunes store app on your phone - does music show as a category there ? If it does but your past purchases aren't showing, then have you changed countries since buying them (content is tied to the country as well as the account), you've tried logging out and back into your account on your phone (tap on your id at the bottom of the Music tab in the iTunes store app), the music is still in your country's store (you can't redownload items that are no longer available), and it's not hidden : http://support.apple.com/kb/HT4919 ?
Or have been keeping and maintaining a backup of your downloads via your computer, which you can use to sync it to your new phone ?