You can certainly create a set of nameservers named after the pattern
ns??.company.com. If you have 5 of them like you show in your example then I don't think I'd list all 5 as NS servers for each of your 800 domains (5 is really more nameservers than you need for a domain) but you could pick amonst them by, for example, using
ns2 on one domain,
ns3 on another domain,
ns5 on a third, and so on.
You should not define
ns5.company.com as CNAME records pointing to the real names of those nameservers. NS records pointing to CNAME records has always been discouraged and might give you trouble. This answer says it's not actually forbidden by the standard, just not recommended.
So make sure
ns5.company.com have A and AAAA records. If they aren't your servers then this means you will have to watch out for the server owner changing the server's address and update your A and AAAA records accordingly if you see it change.
ns5.company.com aren't the servers' real names then it is likely that the reverse DNS entries (PTR records) won't point back to those names. This is perhaps not elegant and I would recommend against doing that for a mail server, but for DNS nothing should really care.
Another way you could handle this is, instead of having more nameservers, you can have the same number of nameservers with more IP addresses each. In other words, instead of adding
ns7.company.com when you want to add your 6th and 7th nameserver, add A and AAAA records for the addresses of the new nameservers to some of the existing 5 names (e.g. if you have 2 new server IP addresses to add, choose 2 out of the 5 existing names and add one IP address to each). This way, all domains that are already delegated to the existing server [names] will get to use the new servers for free.
You can also use any mix of the two strategies: if you have 25 nameservers, have 5 different names with 5 different IP addresses each.