You could also carve a private key into amber (a fossilized resin) which has preserved insects, sometimes for millions of years. Sadly if heated above 200 °C (392 °F), amber suffers decomposition, but I doubt it weathers as badly as stone. Here's a picture of an ant preserved in amber.