Are those sub-domains that appear to be randomly generated really a legit part of your site ?
If not (then as Molis says your site was probably hacked) you are going to have to clean them out and you will probably need help, probably from your site HOST.

You need to speak to your domain HOST about this possible infection/hack as this is commonly as a result of a vulnerability being exploited. e.g. old versions of content management software, PHP, joomla, etc.

You can check some of the analysis sites, http://sitecheck.sucuri.net/scanner/, http://urlquery.net/, http://urlvoid.com/ and enter your domain and see what they bring up.