The notion that mass increases with velocity is not a consequence of Einstein's theory. The erroneous claims that attribute it to Einstein have been disappearing from textbooks for the last 25 years or so, and are now pretty much gone from view. The modern view is that mass does not increase with velocity. Note that we're not talking about a change in the physics here, just in the way we describe it.
You can look at the relativistic factor ##\gamma=\frac{1}{\sqrt{1-v^2/c^2}}## and use it to write expressions like ##\gamma mc^2## for the total energy or ##\gamma mv## for the momentum. What some people used to do is call ##\gamma m## the mass and say that it increases with velocity, but the better way to think about it is to consider ##m## to be the mass, which is constant, and realize that it's ##\gamma## that increases with velocity.