Is such a crypto-system available?
This can be done with RSA where k1 and k2 are encryption keys and f is  multiplication modulo the totient of the public modulus.
The last property, that knowledge of other pairs $k_2'$ and $k_{new}'$ does not reveal $k_1$ is satisfied by using a different modulus for each pair generated.