We currently prevent replay attacks by traversing the entire ancestor chain to figure out whether there is a duplicate transaction. If there is no duplicate transaction with the same (user, timestamp) pair, then we are safe. However, this process becomes computationally expensive as the dag grows.
Thus to improve performance, we make the following change. In each transaction, we add a new field: valid after block number. Each transaction must be included in a block with a block number that is greater than or equal to the valid after block number value. We also check that each transaction in the about-to-be-proposed block has a valid after block number that is less than the block number minus some expiration threshold. This allows us to not have to traverse back more blocks than the expiration threshold to check for duplicate transactions. If there was a block that contains a transaction that is in a block that is further back in the past than the expiration threshold compared to the current block, that transaction cannot be duplicated in the current block as it would be expired (not be valid).
Note that we are using block numbers as a really rough proxy of time. We assume each block contains some minimum amount of gas executed and transaction fee spent, effectively giving us a guarantee that the block took some non-zero time and work to create.