What you quoted in italics is the nameserver's name. You probably have another one set to ns4876.myhostingcompany.com as well. This is used for DNS resolution.
The actual *server* name has to be something else. But, like the nameserver, it can be related to the overall Domain you want to run the server on, if that's what you want.
You said "When I want a new server secured and configured", so I'm assuming you've leased a new dedicated server and are transferring existing site(s) to it? If so...
server.mydomain.com is valid and commonly used. But you can use *almost* any prefix you want, i.e server, host, bling, blah, dazzle, etc. There's at least one restriction on the prefix that I can't quite remember off the top of my head, and *I THINK* involves using a number as the first digit.
Just let the tech know what prefix you want to use for the server name itself, and you should be good to go there.
Some extra info you may find useful:
If your new server is using WHM/cPanel in a default configuration, you'll access WHM using http(s)://chosen-prefix.myhostingcompany.com:2086(2087), cPanel with http(s)://www.myhostingcompany.com:2082(2083), and your site visitors will likely use http(s)://www.myhostingcompany.com/ to view your website or Forum.
If you decide to continue using the same nameservers as before, you often CAN do this though not always. You may want to define new ones in any case. It will take a couple days to propagate all the site moves anyway, so now would be the time to do it if you want to. DNS lookups which now use ns4875.myhostingcompany.com and ns4876.myhostingcompany.com, will start using your new nameservers after the change has propagated.
Hope that helped.