I have an access to my account on VPS over SSH. Some time ago, I changed my password and forgot it. But still, I can log over my SSH key. It was enough for a while, but now I need to login from another device, so it's time to recover my password. How do I change my password without knowing the old one (without root access)?
The short answer is, without knowing your current password and without root/sudo access, you can't change your password. The basic *NIX security model does not allow mortal users to change passwords for accounts they lack the rights to access.
Doing what you want would requite root (sudo) access or at least read access to the passwd and shadow files if you wanted to run cracking software on them.
If you can access your account over your SSH key (not sure what you mean by that), then you will have access to your account and thus, MIGHT be able to change your password with some finagling. For example, creating a trust relationship using .rhost that will allow people with the same username access without requiring a password. Needless to say, this is a dangerous vulnerability and is discouraged.
Most distros that I am aware of require users to know their current password before they can change it. This, again, is part of the basic *NIX security model that has been in effect for around 50 years.
The moral to the story, of course, if to have some sort of a standard username/password management plan so that forgetting your password is recoverable.