I don’t use it in any automation, but in the mqtt integration it has the “Enable will message” option that apparently works fine.
You could set the will message to “Soft restart” and check it when the HA starts.
If topic = “Soft restart” do nothing and set the topic to “Running”
If topic = “Running” HA was not turned off properly, run your automations and set the topic to “Running”.
It wasn’t well explained, but I think it’s enough for you to get the idea.