The checklist is this

Log into your VPS as root

Download the wp-cli binary

curl -O https://raw.githubusercontent.com/wp-cli/builds/gh-pages/phar/wp-cli.phar
https://wp-cli.org/

Make it executable
chmod +x wp-cli.phar

test if it's running
./wp-cli.phar --info

move it to /usr/local/bin/

mv wp-cli.phar /usr/local/bin/wp