In my Amazon Auto-Scaling Group (ASG), when I kill all the servers at once, the Consul cluster is not recovered
When you are killing all the servers at once, it will create an outage which you will need to avoid. You should do it one at a time.
This situation is what Autopilot was added for - you kill a server, ASG adds a new one, Autopilot removes the dead server after the new one is stable. Then repeat this until they’re all updated.
Again, to summarize, you are good as long as you do it slowly and have the Autopilot enabled.
Also note that after Consul version 0.8, the dead server cleanup is enabled by default.