Are brain cells replaced over time?
By brain cells, I'll assume you mean neurons (the other type are called glial cells). Yes, new neurons arise in a least certain parts of the brain, and yes, they do cause memories to weaken or disappear. This has been shown in mice, guinea pigs and degus.

It would be wrong to assume that neurogenesis occurs with the frequency of, say, gastric cell or skin turnover. Up until recently, it was not thought to occur at all.

Learning and remembering use various cortical structures, including the hippocampus.Throughout life, new neurons (neurogenesis) are continuously added to the dentate gyrus. These additions remodel hippocampal circuits, and when this occurs after memory formation, this neurogenesis leads to degradation or forgetting of established memories. This was shown in adult mice. Conversely, decreasing neurogenesis after memory formation decreased forgetting.[1]

It is not only plasticity that makes the brain adaptable to continuous changes in environmental demands. Adult-born neurons integrate into preexisting neuronal networks and participate in information processing. Adult neurogenesis itself is a type of circuit plasticity required for hippocampus-dependent learning and memory recall. Adult hippocampal neurogenesis may also promote forgetting.[2] 

The more neurogenesis there is, the more memories are broken down. Since we retain many memories over our lifetime, it's pretty safe to say out brains don't "turn over" every five years (or even over longer periods); some parts of our brain don't seem to undergo neurogenesis at all.[3]

[1] Hippocampal Neurogenesis Regulates Forgetting During Adulthood and Infancy Science 9 May 2014
[2] A Price to Pay for Adult Neurogenesis Science 9 May 2014
[3] Neurogenesis in the Adult Brain The Journal of Neuroscience February 1, 2002