Mock Database with ID column

I'm (fairly) new to TDD, so be gentle!

I am using CodeFirst to create my application in C# using EF6 in VBS2015 Community.

I have an Interface created for my data access and am able to create a Mock Database in memory for Unit testing.

Each of my Models has a unique identifier column which is named Id (For example, UserID)

Ok, so when I add records to my Mock database, I need to have it create a new ID value for the record, as I reference this in later code. How do I do this with a generic set, when each table has a unique ID column? Do I have to mock out each table independently?

My database interface looks like this:

Namespace Labinator2016.Lib.Headers
{
    using System;
    using System.Collections.Generic;
    using System.Linq;
    public interface ILabinatorDb : IDisposable
    {
        IQueryable<T> Query<T>() where T : class;
        void Add<T>(T entity) where T : class;
        void Delete<T1>(System.Linq.Expressions.Expression<Func<T1, bool>> target) where T1 : class;
        void Remove<T>(T entity) where T : class;
        void Update<T>(T entity) where T : class;
        void SaveChanges();
    }
}

My Mock Database then looks like this:

namespace Labinator2016.Tests.TestData
{
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using Lib.Headers;
    using Labinator2016.Lib.Models;
    class FakeDatabase : ILabinatorDb
    {
        public IQueryable<T> Query<T>() where T : class
        {
            return this.Sets[typeof(T)] as IQueryable<T>;
        }
        public void Dispose() { }
        public void AddSet<T>(IQueryable<T> objects)
        {
            this.Sets.Add(typeof(T), objects);
        }
        public void Add<T>(T entity) where T : class
        {
            this.Added.Add(entity);
            IQueryable<T> temp = this.Sets[typeof(T)] as IQueryable<T>;
            List<T> existing = temp.ToList();
            existing.Add(entity);
            Sets[typeof(T)] = existing;
        }
        void ILabinatorDb.Delete<T1>(System.Linq.Expressions.Expression<Func<T1, bool>> Target)
        {
        }
        public void Update<T>(T entity) where T : class
        {
            this.Updated.Add(entity);
        }
        public void Remove<T>(T entity) where T : class
        {
            this.Removed.Add(entity);
        }
        public void SaveChanges()
        {
            this.saved++;
        }
        public Dictionary<Type, object> Sets = new Dictionary<Type, object>();
        public List<object> Added = new List<object>();
        public List<object> Updated = new List<object>();
        public List<object> Removed = new List<object>();
        public int saved = 0;
    }
}

Currently, I have some code that gets a user object from a user table, based on a name. If it doesn't exist, then one is created first. Here is my code:

User existingUser = this.db.Query<User>().Where(u => u.UserName == newUserName).FirstOrDefault();
if (existingUser == null)
{
    User userToAdd = new User();
    userToAdd.UserName = newUserName;
    userToAdd.Password = PasswordHash.CreateHash("password");
    this.db.Add<User>(userToAdd);
    this.db.SaveChanges();
    existingUser = this.db.Query<User>().Where(u => u.EmailAddress == nu).FirstOrDefault();
}

So, am I using the wrong approach completely in my application, or is there a way to mock out this functionality?