Hi Bharat,
for Step #1 you have to create new segment(s) using valid time chunk(s). If those segments comprise many GB of data then 20 minutes may not be unreasonable to expect to do this operation.
However you do not have to create new segments that are same size as the originals ... if you data is clustered around specific times then you only need re-ingest those times, using valid time partitions ... for example if the data all falls within a couple of one or two hour time chunks on a given day, then you can do a REPLACE/OVERWRITE using just those hours instead of the entire day.
However if your delete is interspersed evenly throughout the data in the segments then you may have no other choice than to do the full replace as you are doing. It looks like Abhishek is asking for info that would relate to performance tuning here.