PostgreSQL 9.6 pg_rewind - takes a long time to replicate
pg_rewind connects to the new master and locates the latest checkpoint it shares with the old master. Then it examines local WAL to find all blocks that have been modified since and copies these blocks from the new master.

So the procedure is slow if


promotion happened a long time ago, so pg_rewind has to dig through many WAL files


or


many blocks have changed since the promotion


From the output of pg_rewind it becomes obvious that half of the blocks in the database cluster have been modified since the slave was promoted. So the problem is that you waited too long after promotion. Immediately after failover, pg_rewind would be much faster.