EF 6 Code-First Many to Many relationship with same entity on non-primary key

Welcome to StackOverflow!

As far as I know, EF cannot handle relationships of this kind.

Your problem isn't that the principal key isn't the primary key. Your main problem is that those keys (TaskTypes) are not unique.

Solution proposal

You can work around this limitation by encapsulating the logic of loading the dependent tasks in a repository. While many people advice against building a repository pattern on top of EF, and most of the times I'm on that side too, this is a great example of why it can be useful.

I would create a method that populates dependencies using LINQ, maybe an extension method, something along the lines of:

private static void LoadDependentTasks(this Task task, IEnumerable<Task> allTasks){
    task.Dependencies = allTasks.Where(yourCustomSelector).ToList();
}

Then in your repository you can use this method on the Tasks you loaded before you return them. E.g:

public Task GetById(Guid taskId){
    Task t = _context.Tasks.Find(taskId);
    t.LoadDependentTasks(_context.Tasks);
}

Then when your business logic calls your repository, it will receive objects that already have their Dependencies property filled.

There is one optimization that is worth mentioning here, though. It isn't as important for getting a single task, but makes a lot of difference when loading all of them. If you implement the GetAll method naively, as follows, it will retrieve the list of Tasks from the server n times, which is not great.

public Task GetAll(){
    List<Task> allTasks = _context.Tasks.ToList();
    foreach(var task in allTasks)
        task.LoadDependentTasks(_context.Tasks);
    return allTasks;
}

You should pass the already existing allTasks variable to the method instead. If - in another scenario - you don't have a list of tasks already, another solution is to call _context.Tasks.Load(), and use _context.Tasks.Load thereafter.