Regardless of whether the backdoor-building of theirs is documented, someone obtained unauthorized access to the machines, be it an employee or not. This means OVH really is compromised, even if they documented the installation of this backdoor.
I'm not entirely sure why they bothered with the root SSH key. If they really wanted they'd just pop open a serial console on the virtual machine wouldn't they?
At the serial console, you end up with a password prompt. It's also easier to just ssh over than to go over to the server and connect a serial cable.