How can users ssh private keys be protected from root stealing and attempting to brute force them? I cannot use selinux as the vendor will not support the app when it's in use? Thanks
Do not give the keys away from your owned and maintained hardware. If you don't have a root on your computer, user Smart Card (or Yubikey).
As already said, nothing protects your keys (or data) from physical access and
root user. Not even SELinux (root can do everything, if is unconfined!). Cryptography does the job only partially (encrypted keys can be brute-forced, but it is not feasible if you have passphrase strong enough). But trusted hardware can not be brute forced and you know exactly when it is used (requires confirmation, pin, whatever).
Take these examples from the book SELinux System Administration --
Consider the example of the shadow file again. A MAC system can be configured so that the file can only be read from and written to by particular processes. A user logged on as root cannot directly access the file or even move it around. He can't even change the attributes of the file:
root# id uid=0(root) gid=0(root)
root# cat /etc/shadow
cat: /etc/shadow: Permission denied
root# chmod a+r /etc/shadow
chmod: changing permissions of '/etc/shadow': Permission denied
This is enforced through rules that describe when the contents of a file can be read. With SELinux, these rules are defined in the SELinux policy and are loaded when the system boots. It is the Linux kernel itself that is responsible for enforcing the rules, and does so through LSM (Linux Security Modules).