The cryptographic hash algorithm MD5 has already begun to be broken, mainly in regards to its collision resistance property, as well as preimage resistance slightly. See the Wikipedia article, in the security section.
Therefore I would not use MD5 for anything slightly security related. A similar story with SHA-1 in that it has began to be broken, so I would use SHA-2 if you do indeed need a hashing algorithm.
The problem with your approach is that you cannot revoke the token from individual devices easily. Also having password as input to your algorithm could make it vulnerable to a hash cracking attack, should the other values be known. Don't rely on your method being secret either, Kerckhoffs's principle states "A cryptosystem should be secure even if everything about the system, except the key, is public knowledge.".
Also another problem with your approach is that your hashing algorithm needs plaintext access to the password, which could suggest you are storing passwords insecurely. In short ensure you are using bcrypt for password storage. Of course, you may be creating the cookie and storing a server-side version of it at a point where the user enters their password, however given that you want to invalidate cookies automatically upon password change makes me think not.
The most secure way to manage devices with tokens is to generate a 128-bit random token per device, and store this hashed with SHA-2 in your database. Ensure a CSPRNG is used to generate the token.
Therefore:
Cookie value: 128-bit token
Database value: SHA-2(128-bit token)
Note that salts are not required for values of such bit strength. Then when a user changes their password, you simply delete all server-side tokens for the user. Additionally, you will be able to allow the user to revoke tokens for different devices individually without any password change required.
The reason for hashing on the server-side is to mitigate any session hijacking should an attacker gain access to your sessions table.