Consul: how to remove dead client nodes quickly
As a best practice, you should gracefully deregister the node gracefully. In this case, consul will know the the node has left and will be removed from the cluster. Otherwise, the consul cannot distinguish between a temporary failure, agent crash, network partition, etc.

There is a github issue as well related to this. 

Quoting few important points from the issue.


  The nodes should automatically reap out after 72hours (not yet configurable, but soon). Otherwise, the best route is to issue a graceful leave before destroying the nodes (consul leave), so that they can be reaped immediately. They are kept around for that long since without a graceful leave, Consul cannot distinguish between a temporary failure, agent crash, network partition, etc.


.


  force-leave should push them into the "left" state. Nodes are not reaped until they are in failed for 72h or in the left state. "force-leave" just moves a node from the "failed" -> "left" state. They are not removed from the members list for 24 or 72h.