Persistent last changed sensor

No it is necessarily complex. As you have pointed out, the last changed attribute is altered at restart.

To get the format you want will be even more complex: