I guess the thing is that deleting everything and recreating it doesn't seem like a problem to me. you can create the new logs containing everything that was in the old logs, except what you don't want to be there. you don't even have to have an algorithm to make up log entries.
I don't see how keys can be time dependent. As you note there will be downtime when keys don't get rotated, and any records of what those downtimes were are subject to being tampered with.